import random
from typing import List


def quick_sort(nums: List[int], l: int, r: int) -> List[int]:
    if l >= r:
        return nums
    index = get_index(nums, l, r)
    quick_sort(nums, l, index)
    quick_sort(nums, index + 1, r)
    return nums

def get_index(nums: List[int], l: int, r: int) -> int:
    left, right = l, r
    temp = nums[l]
    while left < right:
        while right > left and nums[right] >= temp:
            right -= 1
        nums[left] = nums[right]

        while right > left and nums[left] < temp:
            left += 1
        nums[right] = nums[left]

    nums[left] = temp
    return left


if __name__ == '__main__':
    n = 12
    nums = [random.randint(5000000, 10000000) for _ in range(n)]
    print(nums)
    print(quick_sort(nums, 0, n - 1))